package graph.unweighted.bfs.path;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

import graph.unweighted.CandyGraph;
import queue.CandyLoopQueue;


/**
 * 
 * @Title: CandyBFS.java 
 * @Package graph.bsf 
 * @Description: 应用BFS求解无向无权图单源最短路径
 * @author CandyWall   
 * @date 2021年1月15日 下午5:38:11 
 * @version V1.0
 */
public class CandyUnweightedSingleSourceShortestPath {
    private CandyGraph graph;
    private int s;  // 单源路径的源顶点
    private boolean[] visited;
    private int[] pres; // 存储在遍历的过程中每一个顶点的前一个顶点编号
    private int[] distances; // 存储每一个顶点到源顶点的距离
    public CandyUnweightedSingleSourceShortestPath(CandyGraph graph, int s) {
        graph.validateVertex(s);
        this.graph = graph;
        this.s = s;
        visited = new boolean[graph.getVertex_num()];
        pres = new int[graph.getVertex_num()];
        distances = new int[graph.getVertex_num()];
        for(int i = 0; i < graph.getVertex_num(); i++) {
            visited[i] = false;
            pres[i] = -1;
            distances[i] = 0;
        }
        bfs(s);
    }
    
    public int[] getPres() {
        return pres;
    }

    private ArrayList<Integer> bfsOrderList = new ArrayList<>();
    
    public ArrayList<Integer> getBfsOrderList() {
        return bfsOrderList;
    }
    
    /**
     * 判断顶点s到顶点t是否可达
     * @return
     */
    public boolean isConnectedTo(int t) {
        graph.validateVertex(t);
        return visited[t];
    }
    
    /**
     * 获取顶点s到顶点t的单源路径
     * @return
     */
    public ArrayList<Integer> getSingleSourcePath(int t) {
        if(!isConnectedTo(t)) {
            return null;
        }
        ArrayList<Integer> res = new ArrayList<>();
        int cur = t;
        while(cur != s) {
            res.add(cur);
            cur = pres[cur];
        }
        res.add(s);
        Collections.reverse(res);
        return res;
    }
    
    private void bfs(int s) {
        CandyLoopQueue<Integer> queue = new CandyLoopQueue<>();
        queue.enqueue(s);
        visited[s] = true;
        pres[s] = s;
        distances[s] = 0;
        while(!queue.isEmpty()) {
            int v = queue.dequeue();
            bfsOrderList.add(v);
            for(int w : graph.adjacentVertexes(v)) {
                if(!visited[w]) {
                    queue.enqueue(w);
                    visited[w] = true;
                    pres[w] = v;
                    distances[w] = distances[v] + 1;
                }
            }
        }
    }
    
    /**
     * 获取顶点t到顶点s的距离
     * @param t
     * @return
     */
    public int getDistance(int t) {
        graph.validateVertex(t);
        return distances[t];
    }
    
    public static void main(String[] args) {
        CandyGraph graph = new CandyGraph("testData/graph/graph.txt");
        int s = 4;
        CandyUnweightedSingleSourceShortestPath ssp = new CandyUnweightedSingleSourceShortestPath(graph, s);
        System.out.println("从顶点 " + s + " 出发的深度优先遍历的得出的单源路径为：" + Arrays.toString(ssp.getPres()));
        int t1 = 6;
        System.out.println("从顶点 " + s + " 到顶点 " + t1 + " 的路径为：" + (ssp.getSingleSourcePath(t1) == null ? "不可达" : ssp.getSingleSourcePath(t1)));
        System.out.println("从顶点 " + s + " 到顶点 " + t1 + " 的距离为：" + ssp.getDistance(t1));
        int t2 = 5;
        System.out.println("从顶点 " + s + " 到顶点 " + t2 + " 的路径为：" + (ssp.getSingleSourcePath(t2) == null ? "不可达" : ssp.getSingleSourcePath(t2)));
        System.out.println("从顶点 " + s + " 到顶点 " + t2 + " 的距离为：" + ssp.getDistance(t2));
    }
}
